import java.util.Comparator;
import sun.reflect.generics.visitor.Reifier;


public class Node <K extends Comparable<K>,V> 
{
	private Node leftNode = null;
	private Node rightNode = null;
	private K key;
	private V value;

	public Node()
	{

	}

	public Node(V value, K key) 
	{
		this.value = value;
		this.key = key;
	}

	public void setLeftNode(Node<K, V> leftNode)
	{
		this.leftNode = leftNode;
	}

	public int getSize()
	{
		int size = 1;
		if(leftNode != null)
		{
			size = size + leftNode.getSize();
		}
		if(rightNode != null)
		{
			size = size + rightNode.getSize();
		}
		return size;
	}

	public boolean containsKey(K key)
	{
		int cmp = this.key.compareTo(key);
		boolean contains = false;
		if(cmp == 0)
		{
			contains = true;
		}
		else
		{
			if(leftNode != null)
			{
				contains = leftNode.containsKey(key);
			}
			if(contains == false && rightNode != null)
			{
				contains = rightNode.containsKey(key);
			}
		}
		return contains;
	}

	public boolean containsValue(V value)
	{
		boolean contains = false;
		if(this.value.equals(value))
		{
			contains = true;
		}
		else
		{
			if(leftNode != null)
			{
				contains = leftNode.containsValue(value);
			}
			else
			{
				if(rightNode != null)
				{
					contains = rightNode.containsValue(value);
				}
			}
		}
		return contains;
	}

	public int getHeight()
	{
		int height = 1;
		int heightRightNode = 0;
		int heightLeftNode = 0;

		if(rightNode != null)
		{
			heightRightNode = rightNode.getHeight();
		}
		if(leftNode != null)
		{
			heightLeftNode = leftNode.getHeight();
		}

		if( heightRightNode > heightLeftNode )
		{
			if(rightNode != null)
			{	
				height = height + rightNode.getHeight();
			}
		}
		else
		{
			if(leftNode != null)
			{
				height = height + leftNode.getHeight();
			}
		}
		return height;
	}

	public void appendNode(V newValue, int newKey)
	{
		Node<K,V> newNode = new Node(newValue, newKey);
		int cmp = key.compareTo(newNode.getKey());
		if(cmp > 0)
		{
			if(leftNode == null)
			{
				leftNode = new Node(newValue, newKey);
			}
			else
			{
				leftNode.appendNode(newValue, newKey);
			}
		}
		else
		{
			if(rightNode == null)
			{
				rightNode = new Node(newValue, newKey);
			}
			else
			{
				rightNode.appendNode(newValue, newKey);
			}
		}

	}

	public V getValue(K key)
	{
		V returnValue = null;
		if(this.key.compareTo(key) == 0)
		{
			returnValue = value;
		}
		else
		{
			if(leftNode != null)
			{
				returnValue = (V) leftNode.getValue(key);
			}
			if(rightNode != null)
			{
				returnValue = (V) rightNode.getValue(key);
			}
		}
		return returnValue;
	}

	public void remove(K key)
	{
		if(rightNode != null)
		{
			if(rightNode.key.compareTo(key) == 0)
			{
				if(rightNode.isLeaf())
				{
					rightNode = null;
				}
				else
				{
					if(rightNode.getLeftNode() != null)
					{
						rightNode.setLeftNode(rightNode.getRightNode());
						leftNode = leftNode.getLeftNode();
					}
					else
					{
						rightNode = leftNode.getRightNode();
					}
				}
			}
			else
			{
				rightNode.remove(key);
			}
		}
		if(leftNode != null)
		{
			if(leftNode.key.compareTo(key) == 0)
			{
				if(leftNode.isLeaf())
				{
					leftNode = null;
				}
				else
				{
					if(leftNode.getLeftNode() != null)
					{
						leftNode.setLeftNode(leftNode.getRightNode());
						leftNode = leftNode.getLeftNode();
					}
					else
					{
						rightNode = leftNode.getRightNode();
					}
				}

			}
			else
			{
				leftNode.remove(key);
			}
		}
	}

	public void setRightNode(Node rightNode)
	{
		this.rightNode = rightNode;
	}

	public K getKey()
	{
		return key;
	}

	public Node<K,V> getLeftNode()
	{
		return leftNode;
	}

	public Node getRightNode()
	{
		return rightNode;
	}

	public String getValues()
	{
		String values = "";
		if(leftNode != null)
		{
			values = values + " " + leftNode.getValues();
		}
		values = values +" " + value;
		if(rightNode != null)
		{
			values = values + " " + rightNode.getValues();
		}
		return values;
	}

	public String getKeys()
	{
		String keys = null;

		if(leftNode != null)
		{
			keys = keys + " " + leftNode.getKeys();
		}
		keys = keys + " " + key;
		if(rightNode != null)
		{
			keys = keys + " " + rightNode.getKeys();
		}

		return keys;

	}

	public String getTree()
	{
		String retString = null;
		if(leftNode != null && rightNode != null)
		{
			retString = "(" + leftNode.getTree() + " " + key +  " " + rightNode.getTree() + ")";
		}
		if(leftNode == null && rightNode == null)
		{
			retString = "" + key;
		}
		else
		{
			if(leftNode == null && value !=null )
			{
				retString = "("+ key + " " + rightNode.getTree() + ")";
			}
			if(rightNode == null && value !=null )
			{
				retString = "(" + leftNode.getTree() + " " + key + ")";
			}
		}
		return retString;

	}
	
	public boolean isLeaf()
	{
		if(leftNode == null && rightNode == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}
